#define _CRT_SECURE_NO_WARNINGS 1


class Solution
{
public:
    int searchInsert(vector<int>& nums, int target)
    {

        int left = 0, right = nums.size() - 1;
        while (left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] <= target) left = mid;
            else if (nums[mid] > target)right = mid - 1;
        }
        if (nums[left] == target)
            return left;
        else if (nums[left] > target)
            return left;
        else
            return left + 1;
    }
};